home *** CD-ROM | disk | FTP | other *** search
/ ftp.cs.arizona.edu / ftp.cs.arizona.edu.tar / ftp.cs.arizona.edu / icon / newsgrp / group93b.txt / 000012_icon-group-sender _Fri Apr 23 21:04:06 1993.msg < prev    next >
Internet Message Format  |  1993-06-16  |  4KB
  1. Received: by cheltenham.cs.arizona.edu; Sun, 25 Apr 1993 18:21:16 MST
  2. Date: 23 Apr 93 21:04:06 GMT
  3. From: think.com!spdcc!iecc!compilers-sender@uunet.uu.net  (David Gudeman)
  4. Organization: U of Arizona CS Dept, Tucson
  5. Subject: Representations of Dynamic Type Information
  6. Message-Id: <93-04-095@comp.compilers>
  7. Sender: icon-group-request@cs.arizona.edu
  8. To: icon-group@cs.arizona.edu
  9. Status: R
  10. Errors-To: icon-group-errors@cs.arizona.edu
  11.  
  12. I'm preparing a document that is intended to be an encyclopedic summary
  13. of all of the different ways of encoding the type of a value in
  14. dynamically typed languages.  In order to make this list as comprehensive
  15. as possible, I thought I'd post to some relevant groups on the net to see
  16. if anyone has a technique I'm not aware of.  Instead of asking for
  17. techniques and having to go through all of the responses looking for new
  18. ones, I thought I'd list the ones I know about and hope that some
  19. implementers will be willing to go through my list looking for their own
  20. favorite technique, and let me know if it is missing.  Also, many of these
  21. techniques are either folk-lore, or (probably re-)invented by me, so I
  22. would appreciate knowing if anyone can give me references that have some
  23. claim to originiality.
  24.  
  25. I don't need to know about cdr-coding or other methods to represent data,
  26. I'm only interested in methods to encode dynamic type information.
  27.  
  28. If you can help I prefer to get replies by mail.  If you post a follow-up
  29. to this article, please notice that there are a lot of groups in the
  30. subject line, and some replies may not be relevant for some groups (I
  31. recommend comp.lang.misc for general discussions of representational
  32. schemes).
  33.  
  34. Any and all help is greatly appreciated.
  35.  
  36. The LIST:
  37.  
  38. tagged-words (type information is in the machine word)
  39.   tag fields (word is broken up into tag and data fields)
  40.     tag field in high end (most-significant bits) of word
  41.        use tag of all zeros for one type to avoid tagging cost
  42.        negative ints get a tag of all ones, non-negative ints
  43.                                   get a tag of all zeros
  44.        use sign bit for one type
  45.          use sign-bit = 0 for one type and optimize another type by
  46.                                   giving it the tag of all ones in the
  47.                                   high end and tagging by negation.
  48.     tag field in low end of word
  49.       use two-bit tags to represent word pointers to avoid shifting
  50.         use the tag 00 for word pointers to save the cost of tagging
  51.       use all zeros to optimize integer arithmetic
  52.       optimize integer arithmetic by adding/subtracting tag
  53.                                   after subtraction/addition
  54.     tag field in both ends of word
  55.        various combinations of tricks from the other two options
  56.   partitioning by magnitude (type is encoded in the magnitude
  57.                              of the word used to represent it)
  58.     simple range tests to identify types
  59.     segments with statically determined types
  60.     segments with dynamically determined types
  61.       use BIBOP to identify types
  62.       identify type in the segment itself
  63.         first word of segment
  64.         last word of segment
  65. object-pointers (untagged pointers refering to self-identifying blocks
  66.                  on the heap)
  67.   combinations of this scheme with the tagged-word scheme
  68. descriptors (two-word data elements divided into a type word and a
  69.              value word)
  70.   encoding a qualifier in a descriptor
  71.   encoding a cons cell in a descriptor
  72. --
  73. David Gudeman
  74. gudeman@cs.arizona.edu
  75. -- 
  76. Send compilers articles to compilers@iecc.cambridge.ma.us or
  77. {ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.
  78.